A 2-distance k-coloring of a graph G is a mapping from V (G) to the set ofcolors {1,. .. , k} such that every two vertices at distance at most 2 receivedistinct colors. The 2-distance chromatic number $\chi$ 2 (G) of G is then themallest k for which G admits a 2-distance k-coloring. For any finite set ofpositive integers D = {d 1 ,. .. , d k }, the integer distance graph G = G(D)is the infinite graph defined by V (G) = Z and uv $\in$ E(G) if and only if |v-- u| $\in$ D. We study the 2-distance chromatic number of integer distancegraphs for several types of sets D. In each case, we provide exact values orupper bounds on this parameter and characterize those graphs G(D) with $\chi$ 2(G(D)) = {\Delta}(G(D)) + 1.
展开▼
机译：图G的2距离k着色是从V（G）到颜色集{1，的映射。 ..，k}，使得每两个顶点之间的距离最多有2种不同的颜色。那么，G的2距离色数$ \ chi $ 2（G）就是G所允许的2距离k色的最大k。对于任何有限组的正整数D = {d 1，。 ..，d k}，整数距离图G = G（D）是由V（G）= Z和uv $ \ in $ E（G）定义的无限图，当且仅当| v-- u | $ \ in $D。我们研究了几种类型的集合D的整数距离图的2距离色数。在每种情况下，我们都提供此参数的精确值或上限，并用$ \ chi $来表征那些图G（D）。 2（G（D））= {\ Delta}（G（D））+ 1。
展开▼
